package InterviewTest.q0204_partition;
import CommonClass.Common.ListNode;
public class Solution {
    /*
    此题来自于第86题 但是两者有一点不同
    不需要保证分界后两部分的相对位置
     */
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode dummy = new ListNode(0, head);
        /*
        考虑设置两个指针
        pre作为分界点 当pre的next小于x时 就将其抽取出来接到node后面
        否则pre = pre.next;
        这会导致前一部分是倒序的 例如对 1 4 3 2 5 2 x=3
        排列后为2 2 1 4 3 5
         */
        ListNode node = dummy, pre = head;
        while (pre.next != null) {
            if (pre.next.val < x) {
                ListNode temp = pre.next;
                pre.next = temp.next;
                temp.next = node.next;
                node.next = temp;
                node = node.next;
            }else {
                pre = pre.next;
            }
        }

        return dummy.next;
    }
}
